class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: Node
        :rtype: Node
        """
        if head is None:
            return None
        dummyHead = Node(0)
        pre = dummyHead
        cur = head
        node_index_map = {}
        #复制当前节点和next，并保留两个节点的映射关系
        while cur != None:
            node = Node(cur.val)
            node_index_map[cur] = node
            pre.next = node
            pre = node
            cur = cur.next
        cur = head
        cur_new = dummyHead.next
        #复制random
        while cur != None:
            if cur.random != None:
                cur_new.random = node_index_map[cur.random]
            cur = cur.next
            cur_new = cur_new.next
        return dummyHead.next
